class Solution
{
public:
    long long maxBalancedSubsequenceSum(vector<int> &nums)
    {
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            nums[i] -= i;
        }

        map<int, long long> dp;
        dp[nums[0]] = nums[0];
        for (int i = 1; i < n; i++)
        {
            auto it = dp.upper_bound(nums[i]);
            if (it == dp.begin())
            {
                dp[nums[i]] = nums[i] + i;
            }
            else
            {
                it--;
                if (it->second < 0)
                {
                    dp[nums[i]] = nums[i] + i;
                }
                else
                {
                    dp[nums[i]] = it->second + nums[i] + i;
                }
            }
            it = dp.find(nums[i]);
            auto nextIt = it;
            nextIt++;
            while (nextIt != dp.end() && nextIt->second <= it->second)
            {
                nextIt = dp.erase(nextIt);
            }
        }
        return dp.rbegin()->second;
    }
};